This application is based on and hereby claims priority to European Application No. 011 03 455.0, the contents of which are hereby incorporated by reference.
The present invention relates to a data compression method and apparatus and, in particular, but not restricted thereto, relates to a data compression/decompression method and apparatus for embedded devices having a flash-prom.
An increasing number of electronic devices are being provided with embedded devices. Devices such as mobile telecommunications handsets, personal digital assistants and vehicular navigation systems do not support access to data storage systems such as hard or floppy devices and their operating system and applications are typically stored on a flash-PROM that is associated with the embedded device. Flash-proms, also known as non volatile RAM, are typically small and have the ability to retain data, even when a power supply is disconnected. The memory is also instantly erasable in blocks.
Access to a flash-PROM is typically rather slow and a processor would operate at a corresponding rate if it operated by a fetching code directly from the flash-prom. Most boot-loaders, however, copy the code from the flash-PROM into a main memory, which could be for example, an SRAM, DRAM or SDRAM; by executing code from the main memory the processor can work at a much higher speed.
A reduction in the cost of hardware is preferred in all aspects of system design: a flash-PROM is more expensive than standard memories and, accordingly, flash-PROM capacity requirements should be minimized. In use it is preferred that data is compressed. Data compression is employed in several systems where boot-up time is not critical, for example during the start of a Linux kernel. The boot-up time is the period a system requires in order to become operational following switch-on, and a reduction in such time is typically sought for all devices which are regularly switched off. The overall boot-up time is dependent upon the time required to generate a reset, (which is hardware dependent), the time required to transfer a boot image into a memory and the boot-time of a kernel. One problem is that data compression increases boot-up time.
Data compression techniques have been known for many years. One widely known technique was developed by Ziv and Lempel in 1977 (LZ); a further technique by Storer and Szymanski (SS) provides an enhancement of the LZ technique. The basic principle of the LZ technique can be found in many compression utilities such as zip, gzip and arj. A sequence of symbols that occur in a data stream are referenced; subsequent occurrences of such symbol sequences (also denoted as patterns) are replaced by that reference, with the reference typically being shorter than the sequence itself. Presently there are many systems which combine the LZ/SS mechanisms with Huffman coding (Huffman coding enables the efficient storage of frequently used symbols). The combination of LZ/SS mechanisms with Huffman coding, whilst yielding good compression ratios is paid for by a higher runtime.
A still further constraint imposed in system operation is that of verification: a damaged flash-PROM might change a few symbols at random and a device operating with such a flash-PROM may appear to be fully operational but would not operate correctly.
As referred to above, the LZ and SS algorithms are known to provide fast compression and decompression of data. Nevertheless, these processes are not necessarily sufficiently fast for many applications, even with an optimized decompression mechanism written in, for example, assembly code. In order to improve the decompression time further, it has been found necessary to copy not only single bytes, but larger chunks of data at a time. A further complication can occur in the copying of large amounts of data in dword format, for example, since it is required that the source and destination addresses are aligned, i.e. start on an even address. This is not necessarily the case, since uncompressed and compressed blocks might have an odd length.
The present invention seeks to provide an improved data compression/decompression arrangement. The present invention further seeks to provide a data compression/decompression arrangement which reduces flash-PROM usage without increasing boot-up time.
In accordance with a first aspect of the invention, there is provided a method for processing information in a data processor operable to process data to provide a sequence of uncompressed and compressed data blocks, wherein each data block comprises a header part and a data part; wherein the method comprises the steps of:
checking each header part and data part of each processed block to determine whether each part contains an even number of bytes;
wherein, in the event that the number of bytes in any block part is odd, transferring a byte of information required by a subsequent block for each the block part or transferring a header byte of the current block to a previous block; and,
storing the byte information and transferring the byte information to the subsequent or previous block as the subsequent or previous block is processed whereby each block comprises an even number of bytes.
In accordance with another aspect of the invention, there is provided a method for processing information in a data processor operable to process data to provide a sequence of uncompressed and compressed data blocks, the processor comprising a block selection mechanism that selects only blocks with an even distance and an even (data) length, wherein each data block comprises a header part and a data part; wherein the method comprises the steps of:
checking the header part of each processed block to determine whether it contains an even number of bytes;
wherein, in the event that the number of bytes in the header part is odd, transferring a byte of information required by a subsequent block to the current block or transferring a header byte of the current block to a previous block, whereby to ensure that the storage of all blocks have an even number of bytes.
In accordance with another aspect of the invention, there is provided a method of processing information in a data processor operable to provide uncompressed data from a sequence of uncompressed and compressed data blocks, each block having a distance byte and a header byte;
wherein if a block is uncompressed, the data that is following the block header will be copied to a destination pointer, whereby, each time a block of data is processed, the block length that is specified in the block header byte will be added to the destination pointer;
wherein, if a block is compressed, a distance indicator indicates the start location of a pattern which will be copied to the current destination pointer.
Preferably the sequence of a compressed and compressed data blocks are arranged in accordance with a Ziv-Lempel or similar algorithm. For each compressed block, there is a distance indicator associated with the block, which distance indicates the start location of a pattern which will be copied to a current destination pointer. The start location of the pattern can be calculated by the formula:
Pattern start address=current destination pointerxe2x88x92distance.
The length of the pattern can be specified by bits 0-5 of the header byte. The distance may range between 2 and 217xe2x88x922.
The method achieves high performance by employing block alignment: it copies a word and not a byte at a time. If applicable, it can make use of advanced features of the processor it runs on, e.g. data pre-fetching or a reordering of instructions in order to employ the parallel execution of different processor units.
In accordance with a further aspect of the invention, there is provided a data processor operable to process data to provide a sequence of uncompressed and compressed data blocks, wherein each data block comprises a header part and a data part;
wherein the data processor includes a filter operable to check that any header part or data part of a block is an even number of bytes and wherein the data processor is operable, in the event that the number of bytes in any block part being odd, to transfer a byte of information required by a subsequent block to a current block or to transfer a header byte of the current block to a previous block; and,
wherein the processor is operable to store this byte of information, and to transfer this byte of information to the subsequent or previous block as the subsequent or previous block is processed,
whereby the filter is operable to ensure that the data part of a block comprises an even number of bytes and that the header part of the block comprises an even number of bytes.
In accordance with a further aspect of the invention, there is provided a data processor operable to process data to provide a sequence of uncompressed and compressed data blocks, wherein each data block comprises a header part and a data part;
wherein the data processor includes a filter operable to select blocks with an even distance and an even (data) length and wherein the data processor is operable, in the event that the number of bytes in the header part of a block being odd, to transfer a byte of information required by a subsequent block to a current block or to transfer a header byte of the current block to a previous block, guaranteeing that the storage of all blocks along with additional or removed bytes of information (one or none applicable) requires an even number of bytes.
In accordance with a still further aspect of the invention, there is provided a data processor operable to provide uncompressed data from a sequence of uncompressed and compressed data blocks, each block having a distance byte and a header byte; wherein the data processor includes a filter operable to check whether a block of data is compressed or uncompressed;
wherein if a block is uncompressed, the data that is following the block header will be copied to a destination pointer, whereby, each time a block of data is processed, the block length that is specified in the block header byte will be added to the destination pointer; and
wherein, if a block is compressed, a distance indicator indicates the start location of a pattern which will be copied to the current destination pointer.
The sequence of a compressed and compressed data blocks can be arranged in accordance with a Ziv-Lempel or similar algorithm.
The filter (the xe2x80x9ccompressorxe2x80x9d) can take care of there being an even number of data bytes within a block, and the reordering of header bytes of a block with an odd number of these bytes. The search of prior occurrences of a pattern is constrained by the capabilities of the filter: for example, only patterns with an even length and an even distance may be selected. In the event that the number of bytes in a header of a block is odd, a byte of information required by a subsequent block is transferred to the current block whereby the number of header bytes increases by one or a header byte of the current block which is already stored in a previous block whereby the number of header bytes decreases by one.